package 算法.LeetCode91.每日打卡题目;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author: 谢君臣
 * @create: 2021-02-06 14:13
 * @founction: XXXX
 */
public class day06 {
    public static void main(String[] args) {
        System.out.println(maxChunksToSorted(new int[]{2,1,3,4,4}));
    }

    public int maxChunksToSorted1(int[] arr) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        for(int num : arr) {
            if(!stack.isEmpty() && num < stack.getLast()) {
                int head = stack.removeLast();
                while(!stack.isEmpty() && num < stack.getLast()) stack.removeLast();
                stack.addLast(head);
            }
            else stack.addLast(num);
        }
        return stack.size();
    }
    public static int maxChunksToSorted(int[] arr) {
        int sum = 0, i = 1;
        int[] a = Arrays.copyOfRange(arr,0,arr.length);
        Arrays.sort(a);
        while (i <= arr.length) {
            int[] b = Arrays.copyOfRange(arr, 0, i);
            Arrays.sort(b);
            if (chargeArrays(b, Arrays.copyOfRange(a, 0, i))) {
                arr = Arrays.copyOfRange(arr, i, arr.length);
                a = Arrays.copyOfRange(a, i, a.length);
                sum++;
                i = 0;
            }
            i++;
        }
        return sum;
    }

    public static boolean chargeArrays(int[] a, int[] b) {
        return Arrays.toString(a).equals(Arrays.toString(b));
    }
}
